/*
 * @Author: scl
 * @Date: 2023-08-29 21:22:07
 * @LastEditTime: 2023-08-29 22:11:28
 * @Description: file content
 */
/*
 * @lc app=leetcode.cn id=47 lang=typescript
 *
 * [47] 全排列 II
 *
 * https://leetcode.cn/problems/permutations-ii/description/
 *
 * algorithms
 * Medium (65.56%)
 * Likes:    1442
 * Dislikes: 0
 * Total Accepted:    483.3K
 * Total Submissions: 737K
 * Testcase Example:  '[1,1,2]'
 *
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * ⁠[1,2,1],
 * ⁠[2,1,1]]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 * 
 * 
 */

// @lc code=start
function permuteUnique(nums: number[]): number[][] {
    nums.sort((a,b)=>a-b)
    const result:number[][]=[],numArr:number[]=[],len=nums.length,arr:number[]=[],used:number[]=[]
    let k=0
    for(let i=0,j=i;j<len;j++){
        if(nums[j+1]!=nums[i]||j==len-1){
            used.push(j-i+1)
            numArr.push(nums[i])
            i=j+1
        }
    }
    k=numArr.length
    const dfs=(depth)=>{
        if(depth==len){
            result.push([...arr])
            return
        }
        for(let i=0;i<k;i++){
            if(!used[i])continue
            arr.push(numArr[i])
            used[i]--
            dfs(depth+1)
            arr.pop()
            used[i]++
        }
    }
    dfs(0)
    return result
};
// @lc code=end

